package com.glb.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 用 子数组 的方式，求出各种组合的最优解.
 */
public class HB_test5 {
  public static void main(String[] args) {
    // 默认 weight, value 需要有排序.
    int[] weight = { 1, 2, 3, 4 };
    int[] value = { 15, 20, 30, 40 };
    int bagSize = 7;
    // testWeightBagProblem(weight, value, bagSize);

    int maxValue = 0;

    List<List<Integer>> allWeightSubsets = subsets(weight);

    for (List<Integer> weightSubsets : allWeightSubsets) {
      System.out.println(weightSubsets);
      if (weightSubsets.size() == 0) {
        continue;
      }

      if (isMatchBagSize(bagSize, weightSubsets)) {
        int sum = getAllValues(value, weight, weightSubsets);
        if (maxValue < sum) {
          maxValue = sum;
        }
      }
    }

    System.out.println(maxValue);
  }

  private static int getAllValues(int[] value, int[] weight, List<Integer> weightSubsets) {
    int sumValue = 0;
    List<Integer> subSetIndex = new ArrayList<>();
    for (int weightSub : weightSubsets) {
      int index = Arrays.binarySearch(weight, weightSub);
      index = (index < 0)? -1: index;
      subSetIndex.add(index);
    }

    for (int index : subSetIndex) {
      sumValue += value[index];
    }

    return sumValue;
  }

  private static boolean isMatchBagSize(int bagSize, List<Integer> subsetIndexs) {
    int sumWeight = 0;
    for (int index : subsetIndexs) {
      // maxWeight += weight[index];
      sumWeight += index;
    }

    return sumWeight <= bagSize;
  }

  public static List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>()); // Add the empty subset
    for (int num : nums) {
      int size = result.size();
      for (int i = 0; i < size; i++) {
        List<Integer> newSubset = new ArrayList<>(result.get(i));
        newSubset.add(num);
        result.add(newSubset);
      }
    }
    return result;
  }

}
